/*================================================================
*   Copyright (C) 2024 baichao All rights reserved.
*
*   文件名称：main.cpp
*   创 建 者：baichao
*   创建日期：2024年04月07日
*   描    述：
*
================================================================*/

#include <iostream>
#include <set>
#include <utility>

using namespace std;

struct ListNode {
  int32_t val;
  ListNode *next;
  ListNode(int32_t x) : val(x), next(NULL) {}
};

class Solution {
 public:
  ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    int32_t index = 0;
    // 将headA先全部存进set中去。
    for (ListNode *nodeA = headA; nodeA != NULL; nodeA = nodeA->next) {
      m_isExitSet.emplace(nodeA);
    }

    // 再将headB从头开始遍历，存在第一个与set中相等的元素即为相交点，返回。
    for (ListNode *nodeB = headB; nodeB != NULL; nodeB = nodeB->next) {
      if (m_isExitSet.find(nodeB) != m_isExitSet.end()) {
        return nodeB;
      }
    }
    return NULL;
  }
  std::set<ListNode *> m_isExitSet;
};

int main() {
  ListNode *headA, *currNodeA;
  ListNode *headB, *currNodeB;
  currNodeA = headA = new ListNode(4);
  currNodeB = headB = new ListNode(5);
  currNodeA->next = new ListNode(1);
  currNodeA = currNodeA->next;
  currNodeB->next = new ListNode(6);
  currNodeB = currNodeB->next;
  currNodeB->next = new ListNode(1);
  currNodeB = currNodeB->next;

  currNodeA->next = new ListNode(8);
  currNodeA = currNodeA->next;
  currNodeB->next = currNodeA;
  currNodeB = currNodeB->next;

  currNodeA->next = new ListNode(4);
  currNodeA = currNodeA->next;
  currNodeB->next = currNodeA;
  currNodeB = currNodeB->next;

  currNodeA->next = new ListNode(5);
  currNodeA = currNodeA->next;
  currNodeB->next = currNodeA;
  currNodeB = currNodeB->next;

  currNodeA->next = NULL;
  currNodeB->next = NULL;

  Solution solution;
  ListNode *intersectionNode = solution.getIntersectionNode(headA, headB);

  if (intersectionNode) {
    cout << "相交节点的值为: " << intersectionNode->val << endl;
  } else {
    cout << "两个链表无相交节点" << endl;
  }

  // TODO(baichao) 释放内存

  return 0;
}
